#pragma once
#include "BaseSort.h"

template < class T >
class HeapSort : public BaseSort < T >
{
private:
    int m_d;

    inline int MinChild(int i)
    {
        int min = 0;
        if ((i * m_d + 1) >= m_size) min = 0;
        else
        {
            int firstChild = i * m_d + 1 ;
            int tmp1 = (i + 1) * m_d;
            int tmp2 = m_size - 1;
            
            int lastChild = (tmp1 < tmp2) ? tmp1 : tmp2;

            T key = m_data[firstChild];
            min = firstChild;

            for (int i = firstChild; i <= lastChild; ++i)
            {
                if (m_data[i] < key)
                {
                    key = m_data[i];
                    min = i;
                }
            }
        }
        return min;
    }

    inline void Down(int i)
    {
        int minCh = MinChild(i);

        while ((minCh != 0) && (m_data[minCh] < m_data[i]))
        {
            T toSwap = m_data[i];
            m_data[i] = m_data[minCh];
            m_data[minCh] = toSwap;

            i = minCh;
            minCh = MinChild(minCh);
        }
    }

    inline void _Sort()
    {
        int n = m_size;
        
        for (int i = m_size >> 1; i >= 0; --i) Down(i);
        
        while (m_size > 0)
        {
            T toSwap = m_data[0];
            m_data[0] = m_data[m_size - 1];
            m_data[m_size - 1] = toSwap;
            --m_size;
            Down(0);
        }
        m_size = n;
    }


public:
    HeapSort(T* const _data, const int _size, int heapId) 
        : BaseSort(_data, _size), m_d(heapId) {};
    ~HeapSort() {};

    void Sort()
    {
        m_lastTime = GetTickCount();

        _Sort();

        m_lastTime = GetTickCount() - m_lastTime;
    }
};
